package done.normal_901_1000;

import com.study.common.TreeNode;
import org.junit.Test;

import static com.study.util.LogUtil.info;

/**
 * 958. Check Completeness of a Binary Tree 二叉树的完全性检验
 * <p>
 * 给定一个二叉树，确定它是否是一个完全二叉树。
 * <p>
 * 百度百科中对完全二叉树的定义如下：
 * <p>
 * 若设二叉树的深度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，
 * 第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。（注：第 h 层可能包含 1~ 2h 个节点。）
 * <p>
 * 示例 1：
 * 1
 * /   \
 * 2     3
 * / \   /
 * 4   5 6
 * <p>
 * 输入：[1,2,3,4,5,6]
 * 输出：true
 * 解释：最后一层前的每一层都是满的（即，结点值为 {1} 和 {2,3} 的两层），
 * 且最后一层中的所有结点（{4,5,6}）都尽可能地向左。
 * <p>
 * 示例 2：
 * 1
 * /   \
 * 2     3
 * / \     \
 * 4   5     7
 * <p>
 * 输入：[1,2,3,4,5,null,7]
 * 输出：false
 * 解释：值为 7 的结点没有尽可能靠向左侧。
 * <p>
 * 2019-05-11 07:27
 **/
@SuppressWarnings("all")
public class CheckCompletenessOfABinaryTree {

    public boolean isCompleteTree(TreeNode root) {
        // 190512 first
        return true;
    }

    @Test
    public void test() {
        info(isCompleteTree(new TreeNode(1,
                new TreeNode(2,
                        4, 5), new TreeNode(3,
                null, 7))));
    }
}







































/*
public boolean isCompleteTree(TreeNode root) {
    if (root == null)
        return true;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);

    TreeNode temp;
    boolean flag = false;
    while (!queue.isEmpty()) {
        temp = queue.remove();
        if (temp == null){
            flag = true;
            continue;
        }

        // 左空右不空，就报错
        if (flag)
            return false;

        queue.add(temp.left);
        queue.add(temp.right);
    }
    return true;
}
*/
